package com.yww.leetcode.binarysearchtree;

import com.yww.leetcode.common.TreeNode;

import java.util.concurrent.atomic.AtomicInteger;

/**
 * @author yww
 * @description 1008. 前序遍历构造二叉搜索树
 * @since 2024/2/17 15:21
 */
public class BstFromPreorder1008 {
    // 给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。
    // 保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。
    // 二叉搜索树 是一棵二叉树
    // 其中每个节点， Node.left 的任何后代的值 严格小于 Node.val ,
    // Node.right 的任何后代的值 严格大于 Node.val。
    // 二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。
    public TreeNode bstFromPreorder(int[] preorder) {
//        return insert(preorder);
//        return upRecur(preorder, Integer.MAX_VALUE, new AtomicInteger(0));
        return partition(preorder, 0, preorder.length - 1);
    }

    /**
     * 分治法解决
     */
    private TreeNode partition(int[] preorder, int start, int end) {
        if (start > end) {
            return null;
        }
        // 前序的一个元素就是根节点
        int rootVal = preorder[start];
        TreeNode node = new TreeNode(rootVal, null, null);
        // 确定好右子树的起始位置
        int index = start + 1;
        while (index <= end && preorder[index] < rootVal) {
            index++;
        }
        // 构建左子树
        node.left = partition(preorder, start + 1, index - 1);
        // 构建右子树
        node.right = partition(preorder, index, end);
        return node;
    }

    /**
     * 上限法
     * 依次处理 prevorder 中每个值, 返回创建好的节点或 null 作为上个节点的孩子
     * 1. 如果超过上限, 返回 null
     * 2. 如果没超过上限, 创建节点, 并将其左右孩子设置完整后返回
     * i++ 需要放在设置左右孩子之前，意思是从剩下的元素中挑选左右孩子
     */
    private TreeNode upRecur(int[] preorder, int max, AtomicInteger i) {
        if (i.get() == preorder.length) {
            return null;
        }
        int val = preorder[i.get()];
        if (val > max) {
            return null;
        }
        TreeNode node = new TreeNode(preorder[i.get()], null, null);
        i.getAndIncrement();
        node.left = upRecur(preorder, val, i);
        node.right = upRecur(preorder, max, i);
        return node;
    }

    /**
     * 直接插入法插入
     */
    private TreeNode insert(int[] preorder) {
        TreeNode root = new TreeNode(preorder[0], null, null);
        for (int i = 1; i < preorder.length; i++) {
            root = recurInsert(root, preorder[i]);
        }
        return root;
    }

    /**
     * 递归直接插入
     */
    private TreeNode recurInsert(TreeNode cur, int val) {
        if (cur == null) {
            return new TreeNode(val, null, null);
        }
        if (val < cur.val) {
            cur.left = recurInsert(cur.left, val);
        } else if (val > cur.val) {
            cur.right = recurInsert(cur.right, val);
        }
        return cur;
    }
}
